package com.deep.test.sort;

import com.deep.test.util.ArraysUtil;

public class HeapSort {
	
	public static void buildMaxHeap(int[] array){
		if(array==null || array.length<=1){
			return;
		}
		int half = array.length/2;
		for(int i=half;i>=0;i--){
			maxHeap(array,array.length,i);
		}
		for(int i=array.length-1;i>=1;i--){
			ArraysUtil.exchangeElements(array, 0, i);
			maxHeap(array, i, 0);
		}
	}

	private static void maxHeap(int[] array, int heapSize, int index) {
		int left = index*2 +1;
		int right = index*2+2;
		int largest = index;
		if(left<heapSize&&array[left]>array[index]){
			largest = left;
		}
		if(right<heapSize && array[right]>array[largest]){
			largest = right;
		}
		if(index != largest){
			ArraysUtil.exchangeElements(array, index, largest);
			maxHeap(array, heapSize, largest);
		}
		
	}
	public static void main(String[] args) {
		int[] array = {9,12,5,1,8,19,24,14,45,23,120,16,88};
		heapSort(array);
		ArraysUtil.printArray(array);
		
	}

	private static void heapSort(int[] array) {
		if(array==null || array.length<=1){
			return;
		}
		buildMaxHeap(array);
		
	}

}
